package com.sunny.l31;

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> triangle = new ArrayList<>();
        ArrayList<Integer> list1 = new ArrayList<>(Arrays.asList(-1));
        ArrayList<Integer> list2 = new ArrayList<>(Arrays.asList(2,3));
        ArrayList<Integer> list3 = new ArrayList<>(Arrays.asList(1,-1,-3));
        triangle.add(list1);
        triangle.add(list2);
        triangle.add(list3);
        Solution solution = new Solution();
        System.out.println(solution.minimumTotal(triangle));
    }

    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        ArrayList<ArrayList<Integer>> dp = new ArrayList<>();
        for(int i=triangle.size()-1;i>=0;i--){
            ArrayList<Integer> list = new ArrayList<>();
            if(triangle.size()-1 == i){
                list.addAll(triangle.get(i));
            }else{
                for(int j=0; j<triangle.get(i).size(); j++){
                    int tmp = Integer.min(dp.get(0).get(j), dp.get(0).get(j+1));
                    list.add(tmp + triangle.get(i).get(j));
                }
            }
            ArrayList<ArrayList<Integer>> tmpDp = dp;
            dp.clear();
            dp.add(list);
            dp.addAll(tmpDp);
//            System.out.println(list);
        }
        return dp.get(0).get(0);
    }
}
